Draw an example of a binary tree on the board.


What are some applications of binary trees?

	expression evaluation
	Huffman compression
	binary search tree
	priority queue


Give a non-recursive definition of a binary tree.

	a tree where nodes have at most 2 children


Give a recursive definition of a binary tree.

	either empty 
	or composed of a root, a left tree, and a right tree


How many different binary trees are there with exactly 2 nodes?




How do you implement a binary tree data structure?


What should be stored in each binary tree node object?

	reference to the data stored at the node
	reference to the left child
	reference to the right child


Write code for binary tree nodes.




How do you traverse a binary tree in preorder?


How do you traverse a binary tree in postorder?


How do you traverse a binary tree in inorder?


Write code for preorder, postorder, inorder, size, height.





How can you traverse a tree without using recursion?

	use a stack


Write a preorder Iterator for a binary tree.


What happens to the Iterator if you use a Queue instead of a Stack?

	you get level-order instead of preorder


Write a level-order Iterator for a binary tree.





How can you represent an expression as a binary tree?

	leaves are operands
	other nodes are operators


Draw an example expression tree on the board.


How do you construct an expression tree?

	parse the expression


How do you use the tree to evaluate the expression?

	apply the operator at the root to the result of 
	recursively evaluating the left and right subtrees


Write code to evaluate expression trees.